Product Code Database
In the mathematics field of graph theory, a complete graph is a simple graph undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction).; see p. 17
Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, graph drawing of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull.. Such a drawing is sometimes referred to as a mystic rose..
has edges (a triangular number), and is a [[regular graph]] of degree . All complete graphs are their own maximal cliques. They are maximally connected as the only [[vertex cut]] which disconnects the graph is the complete set of vertices. The [[complement graph]] of a complete graph is an [[empty graph]].
If the edges of a complete graph are each given an orientation, the resulting directed graph is called a tournament.
can be decomposed into trees such that has vertices. Ringel's conjecture asks if the complete graph can be decomposed into copies of any tree with edges. This is known to be true for sufficiently large .
The number of all distinct paths between a specific pair of vertices in is givenHassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004. by
where refers to Euler's constant, and
The number of matchings of the complete graphs are given by the telephone numbers
These numbers give the largest possible value of the Hosoya index for an -vertex graph.. The number of of the complete graph (with even) is given by the double factorial ..
The crossing numbers up to are known, with requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project. Rectilinear Crossing numbers for are
through are all [[planar graph]]s. However, every planar drawing of a complete graph with five or more vertices must contain a crossing, and the nonplanar complete graph plays a key role in the characterizations of planar graphs: by Kuratowski's theorem, a graph is planar if and only if it contains neither nor the complete bipartite graph as a subdivision, and by Wagner's theorem the same result holds for [[graph minor]]s in place of subdivisions. As part of the [[Petersen family]], plays a similar role as one of the [[forbidden minor]]s for linkless embedding.. In other words, and as Conway and Gordon proved, every embedding of into three-dimensional space is intrinsically linked, with at least one pair of linked triangles. Conway and Gordon also showed that any three-dimensional embedding of contains a Hamiltonian cycle that is embedded in space as a nontrivial knot.
|
|
